{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Text Justification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fullJustify"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #文本左右对齐"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个单词数组&nbsp;<code>words</code> 和一个长度&nbsp;<code>maxWidth</code>&nbsp;，重新排版单词，使其成为每行恰好有&nbsp;<code>maxWidth</code>&nbsp;个字符，且左右两端对齐的文本。</p>\n",
    "\n",
    "<p>你应该使用 “<strong>贪心算法</strong>” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格&nbsp;<code>' '</code>&nbsp;填充，使得每行恰好有 <em>maxWidth</em>&nbsp;个字符。</p>\n",
    "\n",
    "<p>要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。</p>\n",
    "\n",
    "<p>文本的最后一行应为左对齐，且单词之间不插入<strong>额外的</strong>空格。</p>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>单词是指由非空格字符组成的字符序列。</li>\n",
    "\t<li>每个单词的长度大于 0，小于等于&nbsp;<em>maxWidth</em>。</li>\n",
    "\t<li>输入单词数组 <code>words</code>&nbsp;至少包含一个单词。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>words = [\"This\", \"is\", \"an\", \"example\", \"of\", \"text\", \"justification.\"], maxWidth = 16\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "&nbsp; &nbsp;\"This &nbsp; &nbsp;is &nbsp; &nbsp;an\",\n",
    "&nbsp; &nbsp;\"example &nbsp;of text\",\n",
    "&nbsp; &nbsp;\"justification. &nbsp;\"\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>words = [\"What\",\"must\",\"be\",\"acknowledgment\",\"shall\",\"be\"], maxWidth = 16\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "&nbsp; \"What &nbsp; must &nbsp; be\",\n",
    "&nbsp; \"acknowledgment &nbsp;\",\n",
    "&nbsp; \"shall be &nbsp; &nbsp; &nbsp; &nbsp;\"\n",
    "]\n",
    "<strong>解释: </strong>注意最后一行的格式应为 \"shall be    \" 而不是 \"shall     be\",\n",
    "&nbsp;    因为最后一行应为左对齐，而不是左右两端对齐。       \n",
    "     第二行同样为左对齐，这是因为这行只包含一个单词。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>words = [\"Science\",\"is\",\"what\",\"we\",\"understand\",\"well\",\"enough\",\"to\",\"explain\",\"to\",\"a\",\"computer.\",\"Art\",\"is\",\"everything\",\"else\",\"we\",\"do\"]，maxWidth = 20\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "&nbsp; \"Science &nbsp;is &nbsp;what we\",\n",
    "  \"understand &nbsp; &nbsp; &nbsp;well\",\n",
    "&nbsp; \"enough to explain to\",\n",
    "&nbsp; \"a &nbsp;computer. &nbsp;Art is\",\n",
    "&nbsp; \"everything &nbsp;else &nbsp;we\",\n",
    "&nbsp; \"do &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;\"\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 20</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;由小写英文字母和符号组成</li>\n",
    "\t<li><code>1 &lt;= maxWidth &lt;= 100</code></li>\n",
    "\t<li><code>words[i].length &lt;= maxWidth</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [text-justification](https://leetcode.cn/problems/text-justification/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [text-justification](https://leetcode.cn/problems/text-justification/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"This\", \"is\", \"an\", \"example\", \"of\", \"text\", \"justification.\"]\\n16', '[\"What\",\"must\",\"be\",\"acknowledgment\",\"shall\",\"be\"]\\n16', '[\"Science\",\"is\",\"what\",\"we\",\"understand\",\"well\",\"enough\",\"to\",\"explain\",\"to\",\"a\",\"computer.\",\"Art\",\"is\",\"everything\",\"else\",\"we\",\"do\"]\\n20']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        start = 0\n",
    "        N = len(words)\n",
    "        lineLength = 0\n",
    "        while start < N:\n",
    "            lineLength = len(words[start])\n",
    "            end = start + 1\n",
    "            # two pointers to set start and end pos for the cur line\n",
    "            # build one line by checking possible valid line rlength\n",
    "            while end < N and lineLength + len(words[end]) + (end-start-1) < maxWidth:\n",
    "                lineLength += len(words[end])\n",
    "                end += 1\n",
    "            if end == N  or end == start + 1:\n",
    "                newLine = self.leftJustify(words,start,end,maxWidth,lineLength)\n",
    "                res.append(newLine)\n",
    "            else:\n",
    "                newLine = self.evenlyJustify(words,start,end,maxWidth,lineLength)\n",
    "                res.append(newLine)\n",
    "            # set up the next line start pos\n",
    "            start = end\n",
    "        return res\n",
    "    \n",
    "    def leftJustify(self,words,start,end,maxWidth,lineLength):\n",
    "        neededSpaces = end - start - 1\n",
    "        havingSpaces = maxWidth - lineLength\n",
    "        # to calculate extra spaces\n",
    "        rightSpaces = havingSpaces - neededSpaces\n",
    "        # rebuild the string\n",
    "        string = words[start]\n",
    "        i = start + 1\n",
    "        while i < end:\n",
    "            string += \" \" + words[i]\n",
    "            i += 1\n",
    "        # add extra spaces\n",
    "        string += \" \" * rightSpaces\n",
    "        return string\n",
    "    \n",
    "    def evenlyJustify(self,words,start,end,maxWidth,lineLength):\n",
    "        neededSpaces = end - start - 1\n",
    "        havingSpaces = maxWidth - lineLength\n",
    "        # calculate how many spaces between two words\n",
    "        spacesForEach = havingSpaces//neededSpaces\n",
    "        # extra spaces should be evenly put from left slot till exhausted\n",
    "        leftSpaces = havingSpaces%neededSpaces\n",
    "        string = words[start]\n",
    "        \n",
    "        i = start + 1\n",
    "        \n",
    "        while i < end:\n",
    "            # check if extra spaces is used up or not \n",
    "            if leftSpaces > 0:\n",
    "                string += \" \" + \" \"*spacesForEach + words[i]\n",
    "                leftSpaces -= 1\n",
    "            else:\n",
    "                string += \" \"*spacesForEach + words[i]\n",
    "            i += 1\n",
    "        return string\n",
    "                \n",
    "                \n",
    "                \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words, maxWidth):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :type maxWidth: int\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        lw = len(words)\n",
    "        result = []\n",
    "        while cur < lw:\n",
    "            result_cur = \"\"\n",
    "            i = 0\n",
    "            l = len(words[cur + i])\n",
    "            while (cur + i) < lw and i <= maxWidth - l:\n",
    "                i = i + 1\n",
    "                if (cur+i) < lw:\n",
    "                    l = l + len(words[cur+i])\n",
    "            if cur + i != lw:\n",
    "                l = l - len(words[cur+i])\n",
    "            remain = maxWidth - l\n",
    "            i = i - 1\n",
    "            if i == 0:\n",
    "                result_cur = result_cur + words[cur+i]+ \" \"*(maxWidth-l)\n",
    "            else:\n",
    "                a = remain % i\n",
    "                b = remain // i\n",
    "               \n",
    "                if cur+i+1 != lw:\n",
    "                    for j in range(i+1):\n",
    "                        if j < a:\n",
    "                            result_cur = result_cur + words[cur+j]+ \" \"*(b+1)\n",
    "                        elif j < i:\n",
    "                            result_cur = result_cur + words[cur+j] + \" \"*b\n",
    "                        else:\n",
    "                            result_cur = result_cur + words[cur + j]\n",
    "                else:\n",
    "                    for j in range(i+1):\n",
    "                        if j < i:\n",
    "                            result_cur = result_cur + words[cur+j] + \" \"\n",
    "                        else:\n",
    "                            result_cur = result_cur + words[cur + j] + \" \"*(remain-i)\n",
    "                    \n",
    "            result.append(result_cur)\n",
    "            cur = cur + i + 1\n",
    "        \n",
    "        return result\n",
    "   \n",
    "        \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: 'List[str]', maxWidth: 'int') -> 'List[str]':\n",
    "        res = []\n",
    "        wordLen = []\n",
    "        for i in words:\n",
    "            wordLen.append(len(i))\n",
    "        p = 0\n",
    "        while p < len(words):\n",
    "            pre = p\n",
    "            remain = maxWidth\n",
    "            while p < len(words) and wordLen[p] <= remain:\n",
    "                remain -= wordLen[p]\n",
    "                remain -= 1\n",
    "                p += 1\n",
    "            if p < len(words):\n",
    "                resLine = \"\"\n",
    "                space = maxWidth\n",
    "                wordCount = p - pre\n",
    "                if wordCount == 1:\n",
    "                    resLine = resLine + words[pre] + \" \" * (maxWidth - wordLen[pre])\n",
    "                else:\n",
    "                    for i in range(pre, p):\n",
    "                        space -= wordLen[i]\n",
    "                    base = space // (wordCount - 1)\n",
    "                    spaceCount = [base] * (wordCount - 1)\n",
    "                    tmpSpace = base * (wordCount - 1)\n",
    "                    t = 0\n",
    "                    while tmpSpace < space:\n",
    "                        spaceCount[t] += 1\n",
    "                        t += 1\n",
    "                        tmpSpace += 1\n",
    "                    for i in range(wordCount - 1):\n",
    "                        resLine = resLine + words[pre + i] + \" \" * spaceCount[i]\n",
    "                    resLine = resLine + words[p - 1]\n",
    "                res.append(resLine)\n",
    "            else:\n",
    "                resLine = \"\"\n",
    "                for i in range(pre, p):\n",
    "                    resLine = resLine + words[i]\n",
    "                    if i != p - 1:\n",
    "                        resLine = resLine + \" \"\n",
    "                l = len(resLine)\n",
    "                resLine = resLine + \" \" * (maxWidth - l)\n",
    "                res.append(resLine)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words, maxWidth):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :type maxWidth: int\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if not words:\n",
    "            return list()\n",
    "        \n",
    "        res, row = list(), list()\n",
    "        words_len, count = len(words), 0\n",
    "        i = 0\n",
    "        while i < words_len:\n",
    "            if len(words[i]) + count <= maxWidth:\n",
    "                count += len(words[i]) + 1\n",
    "                row.append(words[i])\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                if len(row) == 1:\n",
    "                    res.append(str(row[0])+' '*(maxWidth - len(row[0])))\n",
    "                else:\n",
    "                    extraSpace = maxWidth - count + len(row)\n",
    "                    num_space = extraSpace//(len(row) - 1)\n",
    "                    pre_space = extraSpace%(len(row) - 1)\n",
    "                    tmp = ''\n",
    "                    for word in row[:-1]:\n",
    "                        if pre_space > 0:\n",
    "                            tmp += str(word) + ' '*(num_space + 1)\n",
    "                            pre_space -= 1\n",
    "                        else:\n",
    "                            tmp += str(word) + ' '*(num_space + 0)\n",
    "                            \n",
    "                    tmp += str(row[-1])\n",
    "                    res.append(tmp)\n",
    "                    \n",
    "                row.clear()\n",
    "                count = 0\n",
    "        tmp = ' '.join(row)  \n",
    "        res.append(tmp + (maxWidth - len(tmp))*' ')\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: 'List[str]', maxWidth: 'int') -> 'List[str]':\n",
    "        res, cur, num_of_letters = [], [], 0\n",
    "        for w in words:\n",
    "            if num_of_letters + len(w) + len(cur) > maxWidth:\n",
    "                for i in range(maxWidth - num_of_letters):\n",
    "                    if len(cur)>1:cur[i%(len(cur)-1)] += ' '\n",
    "                    else:cur[0]+= ' '\n",
    "                res.append(''.join(cur))\n",
    "                cur, num_of_letters = [], 0\n",
    "            cur.append(w)\n",
    "            num_of_letters += len(w)\n",
    "        res.append(' '.join(cur).ljust(maxWidth))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "from operator import add\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        line = ''\n",
    "        for word in words:\n",
    "            if len(line) + len(word) == maxWidth:\n",
    "                line += word\n",
    "                res.append(line)\n",
    "                line = ''\n",
    "            elif len(line) + len(word) < maxWidth:\n",
    "                line += word + ' '\n",
    "            else:\n",
    "                l = self.justify(line, maxWidth)\n",
    "                res.append(l)\n",
    "                line = word + ' '\n",
    "        line = line.strip()\n",
    "        if line:\n",
    "            res.append(line + ' ' * (maxWidth-len(line)))\n",
    "        return res\n",
    "\n",
    "    def justify(self, line: str, maxWidth: int) -> str:\n",
    "        l = line.strip().split(' ')\n",
    "        n = len(l)\n",
    "        count = reduce(add, [len(x) for x in l], 0)\n",
    "        if n == 1:\n",
    "            return l[0] + (maxWidth-count) * ' '\n",
    "        remain = maxWidth - count\n",
    "        i, j = divmod(remain, n-1)\n",
    "        for t in range(j):\n",
    "            l.insert(2*t+1, ' '*(i+1))\n",
    "        for t in range(j, n-1):\n",
    "            l.insert(2*t+1, ' '*i)\n",
    "        return ''.join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        n = len(words)\n",
    "        i = 0\n",
    "        def one_row_words(i):\n",
    "            left = i\n",
    "            cur_row_len = len(words[i])\n",
    "            i += 1\n",
    "            while i<n:\n",
    "                if cur_row_len + len(words[i])+1 > maxWidth:\n",
    "                    break\n",
    "                cur_row_len += len(words[i]) + 1\n",
    "                i += 1\n",
    "            return left,i\n",
    "        while i<n:\n",
    "            left,i = one_row_words(i)\n",
    "            one_row = words[left:i]\n",
    "            if i==n:\n",
    "                res.append(\" \".join(one_row).ljust(maxWidth,\" \"))\n",
    "                break\n",
    "            all_word_len = sum(len(i) for i in one_row)\n",
    "            space_num = i -left - 1\n",
    "            remain_space = maxWidth - all_word_len\n",
    "            if space_num:\n",
    "                a,b = divmod(remain_space,space_num)\n",
    "            tmp = \"\"\n",
    "            for word in one_row:\n",
    "                if tmp:\n",
    "                    tmp += \" \" * a\n",
    "                    if b:\n",
    "                        tmp += \" \"\n",
    "                        b -= 1\n",
    "                tmp += word\n",
    "            res.append(tmp.ljust(maxWidth,\" \"))\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        ans = []   # 最后的答案\n",
    "        cur_c = 0  # 当前行的字母数\n",
    "        cur_w = 0  # 当前行的单词数\n",
    "        wl = []    # 当前行的单词列表\n",
    "        for i, wd in enumerate(words):\n",
    "            l = len(wd)\n",
    "            if cur_c + l + cur_w > maxWidth: # 加上这个单词是否会超过最大长度\n",
    "                if cur_w == 1: # 当前行仅有一个超长的单词，后面全部补空格\n",
    "                    ans.append(wl[0] + ' ' * (maxWidth-cur_c))\n",
    "                else:\n",
    "                    left = maxWidth - cur_c # 这行一共有几个空格\n",
    "                    if left % (cur_w-1) == 0: # 空格刚好平均分配\n",
    "                        ans.append((' '*(left//(cur_w-1))).join(wl))\n",
    "                    else: # 空格不能平均分配\n",
    "                        x = left % (cur_w-1)  # 多余的空格\n",
    "                        b = left // (cur_w-1) # 平均每个间隔最少的空格数\n",
    "                        cans = wl[0]\n",
    "                        for i in range(x): # 前 x 个间隔空 b + 1 个\n",
    "                            cans += ' ' * (b+1) + wl[i+1]\n",
    "                        for i in range(x+1, len(wl)): # 后面的都空 b 个\n",
    "                            cans += ' ' * b + wl[i]\n",
    "                        ans.append(cans)\n",
    "                cur_c = l\n",
    "                cur_w = 1\n",
    "                wl = [wd]\n",
    "            else:\n",
    "                cur_c += l\n",
    "                cur_w += 1\n",
    "                wl.append(wd)\n",
    "\n",
    "        if cur_w > 0: # 所有单词过完了把余下的词放入最后一行\n",
    "            cans = ' '.join(wl)\n",
    "            cans += ' ' * (maxWidth - len(cans))\n",
    "            ans.append(cans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        n = len(words)\n",
    "        i = 0\n",
    "\n",
    "        def one_row_words(i):\n",
    "            # 至少 一行能放下一个单词, cur_row_len\n",
    "            left = i\n",
    "            cur_row_len = len(words[i])\n",
    "            i += 1\n",
    "            while i < n:\n",
    "                # 当目前行 加上一个单词长度 再加一个空格\n",
    "                if cur_row_len + len(words[i]) + 1 > maxWidth:\n",
    "                    break\n",
    "                cur_row_len += len(words[i]) + 1\n",
    "                i += 1\n",
    "            return left, i\n",
    "\n",
    "        while i < n:\n",
    "            left, i = one_row_words(i)\n",
    "            # 该行几个单词获取\n",
    "            one_row = words[left:i]\n",
    "            # 如果是最后一行了\n",
    "            if i == n :\n",
    "                # ljust(width[, fillchar])--默认使用空格在右端填充至指定长度，使得字符串左对齐\n",
    "                res.append(\" \".join(one_row).ljust(maxWidth,\" \"))\n",
    "                break\n",
    "            # 所有单词的长度\n",
    "            all_word_len = sum(len(i) for i in one_row)\n",
    "            # 至少空格个数\n",
    "            space_num = i - left - 1\n",
    "            # 可以为空格的位置\n",
    "            remain_space = maxWidth - all_word_len\n",
    "            # 单词之间至少几个空格,还剩几个空格没用\n",
    "            if space_num:\n",
    "                # a=remain_space//space_num--均匀分配，每个单词之间的空格数\n",
    "                # a=remain_space%space_num--无法均匀分配，多出来要分配给左边的空格数\n",
    "                a, b = divmod(remain_space, space_num)\n",
    "            # 将该行字符串拼接起来\n",
    "            tmp = \"\"\n",
    "            for word in one_row:\n",
    "                if tmp:\n",
    "                    tmp += \" \" * a\n",
    "                    if b:\n",
    "                        # 一个一个分配给左边\n",
    "                        tmp += \" \"\n",
    "                        b -= 1\n",
    "                tmp += word\n",
    "            # tmp.ljust(maxWidth, \" \")--若tmp中只有一个单词，则需要在右边加空格左对齐\n",
    "            res.append(tmp.ljust(maxWidth, \" \"))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        row = []\n",
    "        curr = 0\n",
    "        for word in words:\n",
    "            if curr + len(word) + len(row) <= maxWidth:\n",
    "                curr += len(word)\n",
    "                row.append(word)\n",
    "            else:\n",
    "                if len(row) == 1:\n",
    "                    ans = row[0] + ' ' * (maxWidth - curr)\n",
    "                else:\n",
    "                    blacks = [0 for _ in range(len(row) - 1)]\n",
    "                    black = maxWidth - curr\n",
    "                    while black > 0:\n",
    "                        n = min(black, len(row) - 1)\n",
    "                        for i in range(n):\n",
    "                            blacks[i] += 1\n",
    "                        black -= n\n",
    "                    ans = []\n",
    "                    for i in range(len(blacks)):\n",
    "                        ans.append(row[i])\n",
    "                        ans.append(' ' * blacks[i])\n",
    "                    ans.append(row[-1])\n",
    "                    ans = ''.join(ans)\n",
    "                res.append(ans)\n",
    "                row = [word]\n",
    "                curr = len(word)\n",
    "        if curr > 0:\n",
    "            res.append(' '.join(row) + ' ' * (maxWidth - curr - len(row) + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        ans = []\n",
    "        _row = []\n",
    "        _blank = []\n",
    "        max_row = maxWidth\n",
    "        for word in words:\n",
    "            used = 0\n",
    "            while not used:\n",
    "                if not max_row:\n",
    "                    _ans = ''\n",
    "                    for i in _row:\n",
    "                        if type(i) == int:\n",
    "                            _ans += ' ' * i\n",
    "                        else:\n",
    "                            _ans += i\n",
    "                    ans.append(_ans)\n",
    "                    _row = []\n",
    "                    _blank = []\n",
    "                    max_row = maxWidth\n",
    "                w_l = len(word)\n",
    "                if w_l <= max_row:\n",
    "                    if len(_row) == 0:\n",
    "                        _row.append(word)\n",
    "                        used = 1\n",
    "                        max_row -= w_l\n",
    "                    else:\n",
    "                        if max_row >= (w_l + 1):\n",
    "                            _row.append(1)\n",
    "                            _blank.append(len(_row) - 1)\n",
    "                            _row.append(word)\n",
    "                            used = 1\n",
    "                            max_row -= (w_l+1)\n",
    "                        else:\n",
    "                            i = 0\n",
    "                            while max_row:\n",
    "                                if not len(_blank):\n",
    "                                    _row.append(1)\n",
    "                                    _blank.append(len(_row)-1)\n",
    "                                else:\n",
    "                                    if i == len(_blank):\n",
    "                                        i = 0\n",
    "                                    index = _blank[i]\n",
    "                                    _row[index] += 1\n",
    "                                    i += 1\n",
    "                                max_row -= 1\n",
    "\n",
    "                else:\n",
    "                    i = 0\n",
    "                    while max_row:\n",
    "                        if not len(_blank):\n",
    "                            _row.append(1)\n",
    "                            _blank.append(len(_row) - 1)\n",
    "                        else:\n",
    "                            if i == len(_blank):\n",
    "                                i = 0\n",
    "                            index = _blank[i]\n",
    "                            _row[index] += 1\n",
    "                            i += 1\n",
    "                        max_row -= 1\n",
    "        else:\n",
    "            if _row:\n",
    "                while max_row:\n",
    "                    _row.append(' ')\n",
    "                    max_row -=1\n",
    "                _ans = ''\n",
    "                for i in _row:\n",
    "                    if type(i) == int:\n",
    "                        _ans += ' ' * i\n",
    "                    else:\n",
    "                        _ans += i\n",
    "                ans.append(_ans)\n",
    "\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "\n",
    "        def left_align():\n",
    "            \"\"\" 左对齐 \"\"\"\n",
    "            nonlocal result, line_length\n",
    "            if not line:\n",
    "                return\n",
    "            elif len(line) == 1:\n",
    "                # 一个单词，后面全补空格\n",
    "                result.append(f'{line[0]}{\"\".join([\" \"] * (maxWidth - line_length))}')\n",
    "            else:\n",
    "                # 每个单词间补一个空格，长度不够时后面全补空格\n",
    "                string = \" \".join(line)\n",
    "                result.append(f'{string}{\"\".join([\" \"] * (maxWidth - len(string)))}')\n",
    "\n",
    "        def justify_align():\n",
    "            \"\"\" 两端对齐 \"\"\"\n",
    "            nonlocal result, line_length\n",
    "            # 一个单词使用左对齐\n",
    "            if len(line) < 2:\n",
    "                left_align()\n",
    "                return\n",
    "\n",
    "            # 计算每组单词间需要的空格数量\n",
    "            space_count = maxWidth - line_length\n",
    "            min_space_length = space_count // (len(line) - 1)\n",
    "            extra_space_count = space_count - min_space_length * (len(line) - 1)\n",
    "            space_length_list = [min_space_length] * (len(line) - 1)\n",
    "            for i in range(extra_space_count):\n",
    "                space_length_list[i] += 1\n",
    "\n",
    "            # 每组单词插入指定长度的空格\n",
    "            tmp = []\n",
    "            for i in range(len(line)):\n",
    "                tmp.append(line[i])\n",
    "                if i < len(line) - 1:\n",
    "                    tmp.append(''.join([\" \"] * space_length_list[i]))\n",
    "\n",
    "            result.append(''.join(tmp))\n",
    "\n",
    "\n",
    "        result = []\n",
    "\n",
    "        # 新的一行的所有字符串\n",
    "        line = []\n",
    "        # 上述字符串的总长度\n",
    "        line_length = 0\n",
    "\n",
    "        for i in words:\n",
    "            # 当新的单词不能放入时，应该先将当前存储的字符串输出\n",
    "            if line_length + len(line) + len(i) > maxWidth:\n",
    "                # 两端对齐\n",
    "                justify_align()\n",
    "\n",
    "                # 清空\n",
    "                line = []\n",
    "                line_length = 0\n",
    "\n",
    "            # 加入新的单词\n",
    "            line.append(i)\n",
    "            line_length += len(i)\n",
    "\n",
    "        # 左对齐\n",
    "        left_align()\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        n = len(words)\n",
    "        i = 0\n",
    "\n",
    "        def one_row_words(i):\n",
    "            # 至少 一行能放下一个单词, cur_row_len\n",
    "            left = i\n",
    "            cur_row_len = len(words[i])\n",
    "            i += 1\n",
    "            while i < n:\n",
    "                # 当目前行 加上一个单词长度 再加一个空格\n",
    "                if cur_row_len + len(words[i]) + 1 > maxWidth:\n",
    "                    break\n",
    "                cur_row_len += len(words[i]) + 1\n",
    "                i += 1\n",
    "            return left, i\n",
    "\n",
    "        while i < n:\n",
    "            left, i = one_row_words(i)\n",
    "            # 该行几个单词获取\n",
    "            one_row = words[left:i]\n",
    "            # 如果是最后一行了\n",
    "            if i == n :\n",
    "                res.append(\" \".join(one_row).ljust(maxWidth,\" \"))\n",
    "                break\n",
    "            # 所有单词的长度\n",
    "            all_word_len = sum(len(i) for i in one_row)\n",
    "            # 至少空格个数\n",
    "            space_num = i - left - 1\n",
    "            # 可以为空格的位置\n",
    "            remain_space = maxWidth - all_word_len\n",
    "            # 单词之间至少几个空格,还剩几个空格没用\n",
    "            if space_num:\n",
    "                a, b = divmod(remain_space, space_num)\n",
    "            # print(a,b)\n",
    "            # 该行字符串拼接\n",
    "            tmp = \"\"\n",
    "            for word in one_row:\n",
    "                if tmp:\n",
    "                    tmp += \" \" * a\n",
    "                    if b:\n",
    "                        tmp += \" \"\n",
    "                        b -= 1\n",
    "                tmp += word\n",
    "            #print(tmp, len(tmp))\n",
    "            res.append(tmp.ljust(maxWidth, \" \"))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        def handl_special(word_list, len_all_word, max_width):\n",
    "            left_spaces = max_width - len_all_word - len(word_list) + 1\n",
    "            return \" \".join(word_list) + \" \" * left_spaces\n",
    "\n",
    "        ret = []\n",
    "        curr = []\n",
    "        len_all_curr = 0\n",
    "\n",
    "        for word in words:\n",
    "            if len_all_curr + len(curr) + len(word) > maxWidth:\n",
    "                if len(curr) == 1:\n",
    "                    ret.append(handl_special(curr, len(curr[0]), maxWidth))\n",
    "                else:\n",
    "                    all_spaces = maxWidth - len_all_curr\n",
    "                    each = all_spaces // (len(curr) - 1)\n",
    "                    left = all_spaces - each * (len(curr) - 1)\n",
    "                    for i in range(left):\n",
    "                        curr[i] = curr[i] + \" \"\n",
    "                    ret.append((\" \" * each).join(curr))\n",
    "                curr = []\n",
    "                curr.append(word)\n",
    "                len_all_curr = len(word)\n",
    "            else:\n",
    "                curr.append(word)\n",
    "                len_all_curr += len(word)\n",
    "        if len(curr) > 0:\n",
    "            ret.append(handl_special(curr, len_all_curr, maxWidth))\n",
    "        import logging\n",
    "\n",
    "        logging.debug(f\"\"\" [ret] ==> [{ret}]\"\"\")\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        while words:\n",
    "            stack = []\n",
    "            res_w = maxWidth\n",
    "            while res_w >=  len(words[0]):\n",
    "                stack.append(words.pop(0))\n",
    "                res_w -= len(stack[-1]) + 1\n",
    "                if words == []:\n",
    "                    break\n",
    " \n",
    "            if words == []:\n",
    "                s = stack[0]\n",
    "                for i in stack[1:]:\n",
    "                    s += ' ' + i\n",
    "                s += ' '*(maxWidth - len(s))\n",
    "                res.append(s)\n",
    "            else:\n",
    "                res_w += 1\n",
    "                num_s = len(stack)\n",
    "                s = stack[0]\n",
    "                if num_s != 1:\n",
    "                    dev_space = res_w // (num_s - 1)\n",
    "                    res_space = res_w % (num_s - 1)\n",
    "                    for i in stack[1:]:\n",
    "                        s += ' '*(1 + dev_space + (res_space > 0)) + i\n",
    "                        res_space -= 1\n",
    "                s += ' '*(maxWidth - len(s))\n",
    "                res.append(s)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        ans = []\n",
    "        r = 0\n",
    "        while r < len(words):\n",
    "            l, nChr = r, 0\n",
    "            while r < len(words) and nChr + len(words[r]) + r - l <= maxWidth:\n",
    "                nChr += len(words[r])\n",
    "                r += 1\n",
    "            if r == len(words):  # 当前行是最后一行\n",
    "                s = ' '.join(words[l:r])\n",
    "                s = s + ' ' * (maxWidth - len(s))\n",
    "                ans.append(s)\n",
    "                break\n",
    "            nWord = r - l\n",
    "            nSpace = maxWidth - nChr\n",
    "            if nWord == 1:\n",
    "                ans.append(words[l] + ' ' * nSpace)\n",
    "                continue\n",
    "            avgSpace = nSpace // (nWord - 1)\n",
    "            extraSpace = nSpace % (nWord - 1)\n",
    "            s = words[l]\n",
    "            for i in range(l + 1, r):\n",
    "                s += ' ' * avgSpace\n",
    "                if extraSpace > 0:\n",
    "                    s += ' '\n",
    "                    extraSpace -= 1\n",
    "                s += words[i]\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBlank(self, num):\n",
    "        return \" \"*num\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        right,n = 0,len(words)\n",
    "        ans = []\n",
    "        while True:\n",
    "            sumLen = 0\n",
    "            left = right\n",
    "            while right < n and sumLen + len(words[right])+right-left<= maxWidth:\n",
    "                sumLen += len(words[right])\n",
    "                right +=1\n",
    "            #当前行为最后一行\n",
    "            if right == n:\n",
    "                #单独用s装是因为只有一个单词的时候join是不占空格的\n",
    "                s = \" \".join(words[left:])\n",
    "                ans.append(s +self.getBlank(maxWidth-len(s)))\n",
    "                break\n",
    "            sumSpace = maxWidth-sumLen\n",
    "            sumWord = right-left\n",
    "            #当前行只有一个单词\n",
    "            if sumWord == 1:\n",
    "                ans.append(words[right-1]+self.getBlank(sumSpace))\n",
    "                continue\n",
    "            avgSum = sumSpace // (sumWord-1)\n",
    "            exceptSum = sumSpace % (sumWord-1)\n",
    "\n",
    "             #当前行为中间行\n",
    "            if exceptSum > 0:\n",
    "                ansLeft = self.getBlank(avgSum+1).join(words[left:left+exceptSum+1])\n",
    "                ansRight = self.getBlank(avgSum).join(words[left+exceptSum+1:right])\n",
    "                ans.append(ansLeft + self.getBlank(avgSum) + ansRight)\n",
    "            else:\n",
    "                ans.append(self.getBlank(avgSum).join(words[left:right]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        tmp = \"\"\n",
    "        for i in range(len(words)):\n",
    "            if len(tmp + words[i]) >= maxWidth:\n",
    "                if len(tmp + words[i]) == maxWidth:\n",
    "                    tmp = tmp + words[i]\n",
    "                arr = tmp.strip().split()\n",
    "                len_arr = len(arr)\n",
    "                num_space = maxWidth - len(tmp.strip()) + len_arr - 1\n",
    "                if len_arr == 1:\n",
    "                    arr[0] = arr[0] + num_space * \" \"\n",
    "                    res.append(\"\".join(arr))\n",
    "                else:\n",
    "                    for j in range(num_space):\n",
    "                        arr[j % (len_arr - 1)] = arr[j % (len_arr - 1)] + \" \"\n",
    "                    res.append(\"\".join(arr))\n",
    "                if len(tmp.strip()) < maxWidth:\n",
    "                    tmp = words[i] + \" \"\n",
    "                elif len(tmp.strip()) == maxWidth:\n",
    "                    if len(arr) == 1 and tmp != words[i]:\n",
    "                        tmp = words[i]\n",
    "                    else:\n",
    "                        tmp = \"\"\n",
    "                continue\n",
    "            tmp = tmp + words[i] + \" \"\n",
    "        if tmp:\n",
    "            num_space = maxWidth - len(tmp.strip())\n",
    "            arr = tmp.strip().split()\n",
    "            res.append(\" \".join(arr) + num_space * \" \")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#words = [\"This\", \"is\", \"an\", \"example\", \"of\", \"text\", \"justification.\"]\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words, maxWidth: int):\n",
    "        result = []\n",
    "        #maxWidth = 16\n",
    "        res = []\n",
    "        rest = []\n",
    "        current = 0\n",
    "        word_length = 0\n",
    "        for1 = 4\n",
    "        ozone = 0\n",
    "        for x in words:\n",
    "            q = len(x)\n",
    "            # 实际字符数组分组长度\n",
    "            word_length += q\n",
    "            current += q\n",
    "\n",
    "\n",
    "\n",
    "            if current == maxWidth:\n",
    "                print(\"caocao\")\n",
    "                ozone += 1\n",
    "                rest.append(x)\n",
    "                continue\n",
    "            current += 1\n",
    "\n",
    "\n",
    "            if current > maxWidth:\n",
    "                word_length -= q\n",
    "                print(\"++++\",current,x)\n",
    "                print(rest, word_length)\n",
    "                if word_length != 0:\n",
    "                    res.append((word_length, rest))\n",
    "\n",
    "\n",
    "                word_length = q\n",
    "                #\n",
    "                current = q+1\n",
    "                rest = [x]\n",
    "                continue\n",
    "            ozone += 1\n",
    "            rest.append(x)\n",
    "            print(\"====>\",rest, current)\n",
    "\n",
    "        if len(rest) >= 1:\n",
    "            if word_length>0:\n",
    "                res.append((word_length, rest))\n",
    "            #res[word_length] = rest\n",
    "            #print(rest)\n",
    "        print(res)\n",
    "        ov=0\n",
    "        for x in res:\n",
    "            if x==\"\":\n",
    "                res.remove(x)\n",
    "        print(res)\n",
    "        for l2 in res:\n",
    "            j = l2\n",
    "            content = \"\"\n",
    "\n",
    "            if ov == len(res)-1:\n",
    "                for t in j[1]:\n",
    "                    content += t\n",
    "                    if len(content) < maxWidth:\n",
    "\n",
    "                        content += \" \"\n",
    "                    else:\n",
    "                        break\n",
    "                if len(content) < maxWidth:\n",
    "                    lens = maxWidth-len(content)\n",
    "                    print(\"kkkk\",lens)\n",
    "                    content += \" \"*lens\n",
    "            else:\n",
    "\n",
    "                if len(j[1]) == 1:\n",
    "                    front_more_space = 0\n",
    "                    avg_space = maxWidth-j[0]\n",
    "                else:\n",
    "                    avg_space = (maxWidth-j[0])//(len(j[1])-1)\n",
    "                    front_more_space = (maxWidth - j[0]) % (len(j[1]) - 1)\n",
    "\n",
    "\n",
    "                more_index = 0\n",
    "                mark_index = 0\n",
    "                for z in j[1]:\n",
    "                    if 1 == len(j[1]):\n",
    "                        content += z\n",
    "                        content += \" \" * avg_space\n",
    "                        break\n",
    "                    #print(z)\n",
    "                    content += z\n",
    "                    if mark_index == len(j[1])-1:\n",
    "                        print(\"wocao\")\n",
    "                        print(content)\n",
    "                        break\n",
    "                    content += \" \" * avg_space\n",
    "                    if front_more_space > more_index:\n",
    "                        content += \" \"\n",
    "                        more_index += 1\n",
    "                    mark_index += 1\n",
    "            result.append(content)\n",
    "            ov += 1\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        res = []\n",
    "        curwidth = 0\n",
    "        wordlen = 0\n",
    "        line = []\n",
    "\n",
    "        n = len(words)\n",
    "        def dfs(i, line):\n",
    "            nonlocal curwidth\n",
    "            nonlocal wordlen\n",
    "            if i == n:\n",
    "                res.append([line, wordlen])\n",
    "                return\n",
    "            if curwidth == 0:\n",
    "                temp = curwidth + len(words[i])\n",
    "            else:\n",
    "                temp = curwidth + len(words[i]) + 1\n",
    "            \n",
    "            if temp > maxWidth:\n",
    "                res.append([line, wordlen])\n",
    "                line = []\n",
    "                curwidth = 0\n",
    "                wordlen = 0\n",
    "                dfs(i, line)\n",
    "            else:\n",
    "                wordlen += len(words[i])\n",
    "                curwidth = temp\n",
    "                line.append(words[i])\n",
    "                # print(i, line, curwidth)\n",
    "                dfs(i+1, line)\n",
    "\n",
    "        # 划分单词, 计算长度\n",
    "        dfs(0, line)\n",
    "        # 填充空格\n",
    "        resstr = []\n",
    "        for w in range(len(res)):\n",
    "            lineword, wlen = res[w]\n",
    "            # print(lineword, wlen)\n",
    "            k = maxWidth - wlen\n",
    "            if w != len(res)-1:\n",
    "                i = 0\n",
    "                if len(lineword) > 1:\n",
    "                    while k > 0:\n",
    "                        if i == len(lineword) - 1:\n",
    "                            i = 0\n",
    "                        lineword[i] += \" \"\n",
    "                        k -= 1\n",
    "                        i += 1\n",
    "                        # print(i, k, lineword)\n",
    "                else:\n",
    "                    lineword = [lineword[0] + \" \" * k]\n",
    "            else:\n",
    "                for i in range(len(lineword)-1):\n",
    "                    lineword[i] += \" \"\n",
    "                lineword[-1] += (\" \") * (k-len(lineword)+1)\n",
    "\n",
    "\n",
    "            # finallen = sum([len(x) for x in lineword])\n",
    "            # print(lineword, finallen)\n",
    "            resstr.append(\"\".join(lineword))\n",
    "        return resstr\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# blank 返回长度为 n 的由空格组成的字符串\n",
    "def blank(n: int) -> str:\n",
    "    return ' ' * n\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        ans = []\n",
    "        right, n = 0, len(words)\n",
    "        while True:\n",
    "            left = right  # 当前行的第一个单词在 words 的位置\n",
    "            sumLen = 0  # 统计这一行单词长度之和\n",
    "            # 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格\n",
    "            while right < n and sumLen + len(words[right]) + right - left <= maxWidth:\n",
    "                sumLen += len(words[right])\n",
    "                right += 1\n",
    "\n",
    "            # 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格\n",
    "            if right == n:\n",
    "                s = \" \".join(words[left:])\n",
    "                ans.append(s + blank(maxWidth - len(s)))\n",
    "                break\n",
    "\n",
    "            numWords = right - left\n",
    "            numSpaces = maxWidth - sumLen\n",
    "\n",
    "            # 当前行只有一个单词：该单词左对齐，在行末填充空格\n",
    "            if numWords == 1:\n",
    "                ans.append(words[left] + blank(numSpaces))\n",
    "                continue\n",
    "\n",
    "            # 当前行不只一个单词\n",
    "            avgSpaces = numSpaces // (numWords - 1)\n",
    "            extraSpaces = numSpaces % (numWords - 1)\n",
    "            s1 = blank(avgSpaces + 1).join(words[left:left + extraSpaces + 1])  # 拼接额外加一个空格的单词\n",
    "            s2 = blank(avgSpaces).join(words[left + extraSpaces + 1:right])  # 拼接其余单词\n",
    "            ans.append(s1 + blank(avgSpaces) + s2)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        cnt=0\n",
    "        l=[]\n",
    "        res=[]\n",
    "        def fun(l:List[str]) -> str:\n",
    "            if len(l)==1:\n",
    "                s=l[0]\n",
    "                s+=' '*(maxWidth-len(s))\n",
    "                return s\n",
    "            else:\n",
    "                c=maxWidth-sum(len(i) for i in l)\n",
    "                k=floor(c/(len(l)-1))\n",
    "                d=c-k*(len(l)-1)\n",
    "                s=''\n",
    "                for i in range(d):\n",
    "                    s+=l[i]+(' '*(k+1))\n",
    "                for i in range(d,len(l)-1):\n",
    "                    s+=l[i]+(' '*k)\n",
    "                s+=l[-1]\n",
    "                return s\n",
    "        def end(l:List[str]) -> str:\n",
    "            s=' '.join(l)\n",
    "            s+=' '*(maxWidth-len(s))\n",
    "            return s\n",
    "        for i in words:\n",
    "            if cnt+len(i)<=maxWidth:\n",
    "                l.append(i)\n",
    "                cnt+=len(i)+1\n",
    "            else:\n",
    "                res.append(fun(l))\n",
    "                l.clear()\n",
    "                l.append(i)\n",
    "                cnt=len(i)+1\n",
    "        res.append(end(l))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        def concate(seg: List[str], center:bool=True) -> str:\n",
    "            if len(seg) == 1:\n",
    "                return seg[0].ljust(maxWidth, ' ')\n",
    "            if not center:\n",
    "                return ' '.join(seg).ljust(maxWidth, ' ')\n",
    "            sumlen = 0\n",
    "            for s in seg: sumlen += len(s)\n",
    "            avg = (maxWidth-sumlen) // (len(seg)-1)\n",
    "            amd = (maxWidth-sumlen) % (len(seg)-1)\n",
    "            res = seg[0]\n",
    "            for i in range(1, len(seg)):\n",
    "                res += ''.ljust(avg, ' ') + (' ' if i <= amd else '') + seg[i]\n",
    "            return res\n",
    "        \n",
    "        ans = []\n",
    "        seg = []\n",
    "        slen = 0\n",
    "        for i in range(len(words)):\n",
    "            if slen + (1 if seg else 0) + len(words[i]) > maxWidth:\n",
    "                ans.append(concate(seg))\n",
    "                slen = 0\n",
    "                del seg[:]\n",
    "            slen += (1 if seg else 0) + len(words[i])\n",
    "            seg.append(words[i])\n",
    "        ans.append(concate(seg, False))\n",
    "        return ans        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
